﻿using UnityEngine;
using System.Collections.Generic;
using System.Collections;

namespace COC.Tools.Pathing.Misc
{
    public class CBinaryHeap
    {
        public PathNode[] mBinaryHeap;
        public int numberOfOpenList = 0;
       public CBinaryHeap(int row,int column)
        {
            mBinaryHeap=new PathNode[row*column+2];
           /* PathNode p=new PathNode();
            for (int i = 0; i < mBinaryHeap.GetLength(); i++)
            {
                mBinaryHeap[i] = p;
            }*/

        }
       public void clear()
       {
           numberOfOpenList = 1;
       }
       public PathNode addNode(PathNode node)
       {
           int m = numberOfOpenList;
           PathNode tempNode=null;
           mBinaryHeap[numberOfOpenList] = node;
           while(m!=1)
           {
               if (mBinaryHeap[m].fCost <= mBinaryHeap[m >> 1].fCost)
               {
                   tempNode= mBinaryHeap[m];
                   mBinaryHeap[m] = mBinaryHeap[m / 2];
                   mBinaryHeap[m / 2] = tempNode;
                   m /= 2;
               }
               else 
                   break;
           }
           numberOfOpenList++;
           return node;
       }
       public PathNode removeNode()
       {
           numberOfOpenList--;
           int u ,v=1;
           PathNode tempNode=mBinaryHeap[1];
           mBinaryHeap[1]=mBinaryHeap[numberOfOpenList];
           do
           {
               u = v;
               //if exist both children
               if (2 * u + 1 <= numberOfOpenList)
               {
                   if (mBinaryHeap[u].fCost >= mBinaryHeap[2 * u].fCost)
                       v = 2 * u;
                   if (mBinaryHeap[v].fCost >= mBinaryHeap[2 * u + 1].fCost)
                       v = 2 * u + 1;
               }
               //if exsit one child
               else if (2 * u <= numberOfOpenList)
               {
                   if (mBinaryHeap[v].fCost >= mBinaryHeap[2 * u].fCost)
                   {
                       v = 2 * u;
                   }
               }
               if (u != v)
               {
                   tempNode=mBinaryHeap[u];
                   mBinaryHeap[u] = mBinaryHeap[v];
                   mBinaryHeap[v]=tempNode;
               }else 
                   break;

           } while (true);
           return tempNode;
       }
        public void rearrange()
        {
            int change=0;
            for (int i = 2; i < numberOfOpenList; i++)
            {
                    PathNode tmpValue = mBinaryHeap[i];
                    int bubbleIndex = i;
                    
                    while (bubbleIndex != 1)
                    {
                        int parentIndex = bubbleIndex / 2;

                        if (mBinaryHeap[i].fCost <= mBinaryHeap[parentIndex].fCost)
                        {
                            tmpValue = mBinaryHeap[parentIndex];
                            mBinaryHeap[parentIndex] = mBinaryHeap[bubbleIndex];
                            mBinaryHeap[bubbleIndex] = tmpValue;
                            bubbleIndex = parentIndex;
                            change++;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }
        }


    }

